题目 进击的奶牛 跳石头 午枫爱搬家 探险 Kingdom Game I 勇敢的冒险者
进击的奶牛
题目大意
给定一个一维坐标系上的 nnn 个牛棚位置,编号为 x1,x2,…,xnx_1, x_2, \dots, x_nx1 ,x2 ,…,xn ,你要在这些位置中安排 ccc 头牛。要求这些牛必须分配到不同的牛棚,且任意两头牛的最近距离尽可能大。
请你求出,在最优安排下,这个“最近的两头牛的最小距离”的最大值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这是一个经典的“最大化最小值”类型问题:
* 所有牛必须放进牛棚(数量不够是不合法的);
* 安排时,要求任意两头牛之间的最近距离尽可能大;
* 我们要最大化这个最近距离的最小值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
本题可以使用 二分答案 + 贪心判断 来求解。
1. 二分答案
* 设我们要找的答案为 ddd:所有牛之间的最近距离不小于 ddd。
* 我们对 ddd 进行二分查找,枚举可能的最近距离 ddd,检查是否可行。
2. 贪心验证(CHECK 函数)
* 将牛棚的位置排序;
* 然后从最左边开始放牛,尽可能让每头牛之间的距离 ≥ ddd;
* 如果能放下 ccc 头牛,说明当前 ddd 可行。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 排序:O(nlogn)O(n \log n)O(nlogn);
* 二分次数:最多 log(最大距离)=log(1e9)\log(\text{最大距离}) = \log(1e9)log(最大距离)=log(1e9),约为 30;
* 每次 check:线性扫一遍 nnn 个牛棚,O(n)O(n)O(n);
* 总复杂度为 O(nlogD)O(n \log D)O(nlogD),DDD 为最大距离。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
跳石头
题目大意
给定一个总长为 LLL 的河流,起点为 000,终点为 LLL,中间有 NNN 块岩石,每块岩石的位置为 DiD_iDi (满足 0<Di<L0 < D_i < L0<Di <L,已升序给出)。
你可以最多移除 MMM 块岩石,目的是使得最终从起点跳到终点所经过的每一跳中,最短的跳跃距离尽可能大。
输出在最优移除策略下,这个“最短跳跃距离”的最大可能值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这是一道典型的“最大化最小值”类型的问题。我们需要在跳跃过程中最大化最短跳跃距离,而要做到这一点,就必须利用二分答案 + 贪心判断的套路:
* 最大化最小跳跃距离 ⇒\Rightarrow⇒ 二分答案;
* 是否能移除 ≤ M 块石头,使得每次跳跃距离都 ≥ x? ⇒\Rightarrow⇒ 贪心 check。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
STEP 1: 二分答案
我们要找一个最大的 xxx,使得在移除不超过 MMM 块岩石后,跳跃过程中每一跳的距离都不少于 xxx。
* 答案范围是 [1,L][1, L][1,L];
* 用二分法枚举这个 xxx;
* 每次二分中间值 mid 后,判断是否能在跳跃过程中保证最短跳跃距离 ≥ mid;
* 如果可以,就尝试更大的 mid;
* 如果不行,就尝试更小的 mid。
STEP 2: 贪心判断 CHECK(MID)
我们从起点开始向终点跳:
* 每次尽量跳到“最远但距离不小于 mid 的岩石”;
* 如果当前位置到下一个岩石的距离 < mid,就必须移除这个岩石;
* 贪心地尝试跳远,统计移除了多少块石头;
* 最终判断移除的数量是否 ≤ M。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 二分次数最多 log2L≈30\log_2 L \approx 30log2 L≈30;
* 每次 check 遍历所有岩石一次,O(N)O(N)O(N);
* 整体时间复杂度为 O(NlogL)O(N \log L)O(NlogL),对于 N≤5×104N \leq 5 \times 10^4N≤5×104、L≤109L \leq 10^9L≤109 可以接受。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
午枫爱搬家
题目大意
给定 nnn 个物品的重量,按照顺序搬运,最多搬 kkk 次。每次搬的物品总重量不能超过某个上限 SSS。要求求出使得在最多搬 kkk 次的前提下,该最大重量上限 SSS 的最小值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这是一个经典的「最小化最大值」问题 —— 把 nnn 个物品顺序分成 kkk 段,每段的总和不超过某个值 SSS,求满足条件的最小 SSS。
可以使用 二分答案 + 贪心判断 来解决。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 二分上限 SSS 的值,下限为最大单个物品的重量,上限可以设得较大,例如 101410^{14}1014。
2. 贪心判断是否可行:
* 从前往后搬物品,如果当前搬运重量加上一个物品超过了当前尝试的 SSS,就开始新的一次搬运。
* 如果搬运次数不超过 kkk 次,则当前的 SSS 是可行的。
3. 更新答案:
* 如果当前 SSS 可行,就尝试更小的 SSS;
* 否则增大 SSS。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 二分查找复杂度为 log(max sum)\log(\text{max sum})log(max sum),最多约 606060 次;
* 每次 check 是 O(n)O(n)O(n);
* 总体复杂度为 O(nlog(sum))O(n \log(\text{sum}))O(nlog(sum)),对于 n≤2×105n \leq 2 \times 10^5n≤2×105 是可以接受的。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
探险
题目大意
有 nnn 个探险队员,每个队员的体力值为 aia_iai ,要将他们分为 kkk 个连续的小组。你需要将所有人分完,且每组必须连续排列。请你设计一种分组方式,使得所有组中体力和最小的一组的体力和最大。
输出这个最大值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 分组必须是连续的(不能随意选择某几个)。
* 所有人必须分组,不可遗漏。
* 目标是最大化所有组中体力和最小的一组的值。
* 实质是一个“最大化最小值”的问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
这个问题可以通过二分答案 + 贪心验证解决:
1. 设定一个答案范围:我们设最小体力和为 xxx,想知道是否能划分出 kkk 个小组,每组体力和 ≥ xxx。
2. 二分搜索:对 xxx 进行二分查找,寻找最大可行值。
3. 贪心验证 check(x):
* 顺序遍历每个人的体力值,累计小组和。
* 当累计和 ≥ xxx,就认为当前一组划分完毕,重置累计和。
* 最终统计划分出的组数是否 ≥ kkk,若是,说明当前 xxx 可行。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 二分搜索复杂度:O(log(∑ai))O(\log(\sum a_i))O(log(∑ai )),最多为 log(3×108)≈30\log(3 \times 10^8) \approx 30log(3×108)≈30
* 每次 check 复杂度:O(n)O(n)O(n),需要线性遍历整个数组
* 总体复杂度:O(nlog(∑ai))O(n \log(\sum a_i))O(nlog(∑ai )),足以应对 n≤3×104n \leq 3 \times 10^4n≤3×104
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
KINGDOM GAME I
题目大意
给出 nnn 个居民,每人有生活成本 wiw_iwi 和对王国的贡献 viv_ivi 。
若居民被分配的生活成本 SSS 小于 wiw_iwi ,他会叛乱,对王国造成 viv_ivi 的负贡献(变成 −vi-v_i−vi );
若 S≥wiS \ge w_iS≥wi ,他对王国的正面贡献变为 k⋅vik \cdot v_ik⋅vi ,其中 k=⌊Swi⌋k = \left\lfloor \frac{S}{w_i} \right\rfloork=⌊wi S ⌋。
问:最小的 SSS(每个人都分配一样的 SSS)是多少,使得总贡献 ∑\sum∑ 不小于 MMM?
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
每个人的贡献函数关于 SSS 是分段函数:
* 当 S<wiS < w_iS<wi ,贡献是 −vi-v_i−vi
* 当 S≥wiS \ge w_iS≥wi ,贡献是 ⌊Swi⌋⋅vi\left\lfloor \frac{S}{w_i} \right\rfloor \cdot v_i⌊wi S ⌋⋅vi
目标是找到最小的 SSS,使得总贡献 ≥M\ge M≥M。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
二分答案:
* SSS 的最小值为 000,最大可以设为 1e9+71e9+71e9+7(显然超过所有 wiw_iwi )。
* 每次取中间值 mid:
* 计算对于所有人,以 S=midS = midS=mid 时的总贡献值;
* 若总贡献 ≥M\ge M≥M,说明当前 SSS 是可行解,尝试更小;
* 否则增大 SSS。
check 函数逻辑:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 二分查找次数:log2(109)≈30\log_2(10^9) \approx 30log2 (109)≈30
* 每次 check 遍历 nnn 个人,总共约 30×n30 \times n30×n 次操作。
* 对于 n≤2×105n \le 2 \times 10^5n≤2×105 是可以接受的。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
勇敢的冒险者
题目大意
一个人站在数轴的 0 点,每次跳跃可以选择:
* 向前跳 kkk(第 kkk 次跳跃时)
* 向后跳 1
第 kkk 次跳跃的前跳步数是 kkk,而后跳始终是 −1-1−1。问:最少需要多少次跳跃,才能到达目标位置 xxx(x>0x > 0x>0)?
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
每次跳跃有两个选择,但显然:
* 多数时候我们优先前跳,速度更快
* 如果前跳过头了,可以用 −1-1−1 补回来
我们要求最小跳跃次数 kkk,使得从 000 出发,经过最多 kkk 步可以到达 xxx
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
STEP 1:前跳求和
设我们只使用前跳,总共跳 kkk 次,跳到的位置是:
Sk=1+2+⋯+k=k(k+1)2S_k = 1 + 2 + \dots + k = \frac{k(k+1)}{2}Sk =1+2+⋯+k=2k(k+1)
这个是前 kkk 次的最大可能位置。
我们希望:
Sk≥xS_k \ge xSk ≥x
那么最小的 kkk 满足这个条件,是候选答案。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
STEP 2:考虑能否通过后跳调整
前跳总步数是 SkS_kSk ,但我们可以在后面某些跳中选择 −1-1−1,让总距离变为 xxx。
也就是说,如果:
Sk−x≠1S_k - x \ne 1Sk −x=1
那么就可以通过把某个 +k+k+k 换成 −1-1−1 的方式,使得恰好跳到 xxx。
把 +k+k+k 换成 −1-1−1 的过程,总共损失了 k+1k+1k+1 步,所以对任意Sk−x>1S_k-x > 1Sk −x>1,都有 kkk 使得 k****k−xk****_k-xk****k −x 。
但如果:
Sk−x=1S_k - x = 1Sk −x=1
无法调整出来(因为 k=1k = 1k=1 时,k+1=2>1k+1 = 2 > 1k+1=2>1)。
结论:
* 若 Sk=xS_k = xSk =x,刚好跳到:答案是 kkk
* 若 Sk>xS_k > xSk >x 且 Sk−x≠1S_k - x \ne 1Sk −x=1,可以通过换跳调整:答案是 kkk
* 若 Sk−x=1S_k - x = 1Sk −x=1,不能调整,需要多跳 1 步:答案是 k+1k+1k+1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
STEP 3:使用二分找最小 KKK
我们要找到满足 k(k+1)2≥x\frac{k(k+1)}{2} \ge x2k(k+1) ≥x 的最小 kkk,可以用二分法来优化。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 每个测试用例:
* 二分 kkk:最多 log2(2x)\log_2(\sqrt{2x})log2 (2x ) 次
* 时间复杂度为 O(logx)O(\log x)O(logx)
* 总体复杂度:O(t⋅logx)O(t \cdot \log x)O(t⋅logx),对于 t=1000,x≤106t = 1000, x \le 10^6t=1000,x≤106,可接受
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示